#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <sys/mman.h>
#include <fcntl.h>
#include <sys/stat.h>
#include <sys/time.h>

/*
 * Results are collected first and printed later, so that time measurements
 * do not include calls to printf().
 *
 * This uses a rather primitive data-structure without dynamic memory
 * management, but at least overflows will be detected.
 *
 * (When using multiple threads, make sure that you do not run into race
 * conditions.)
 */

struct result {
	int idx_a;
	int idx_b;
	int length;
};

#define MAX_RESULTS 1000
struct result_container {
	int current;
	int overflow;
	char *data_a;
	char *data_b;
	struct result r[MAX_RESULTS];
};

void init_result_container(struct result_container *rc, char *data_a, char *data_b)
{
	rc->current = 0;
	rc->overflow = 0;
	rc->data_a = data_a;
	rc->data_b = data_b;
}

void collect_result(struct result_container *rc, int a, int b, int len)
{
	if (rc->current >= MAX_RESULTS) {
		++rc->overflow;
		return;
	}
	rc->r[rc->current].idx_a = a;
	rc->r[rc->current].idx_b = b;
	rc->r[rc->current].length = len;

	++rc->current;
}

void print_results(struct result_container *rc, int verbose)
{
	int i, k;

	for (i = 0; i < rc->current; ++i) {
		struct result *r = &rc->r[i];

		printf("%d %d %d", r->idx_a + 1 - r->length,
					r->idx_b + 1 - r->length, r->length);
		if (verbose) {
			printf(": \"");
			for (k = 0; k < r->length; ++k) {
				printf("%c", rc->data_a[r->idx_a + 1 + k - r->length]);
			}
			printf("\"");
		}
		printf("\n");
	}
	if (rc->overflow)
		printf("Warning: %d results were lost, increase MAX_RESULTS.\n", rc->overflow);
}



int main(int argc, char **argv)
{
	int fd_a, fd_b;
	char *data_a, *data_b;
	struct stat stat_a, stat_b;
	int ret, K, verbose;

	/* "Parse" arguments */
	if (argc != 4 && argc != 5) {
		printf("usage: %s <file A> <file B> <K> [ -v ]\n", argv[0]);
		return 0;
	}

	/* Minimum length of matches to collect */
	K = atoi(argv[3]);

	/* Amount of output */
	verbose = argc == 5;

	/* Open input files, determine their sizes, and mmap() them into memory */
	fd_a = open(argv[1], O_RDONLY);
	if (fd_a == -1) {
		perror(argv[1]);
		return 1;
	}
	fd_b = open(argv[2], O_RDONLY);
	if (fd_b == -1) {
		perror(argv[2]);
		return 1;
	}

	ret = fstat(fd_a, &stat_a);
	if (ret == -1) {
		perror("fstat A");
		return 1;
	}
	ret = fstat(fd_b, &stat_b);
	if (ret == -1) {
		perror("fstat B");
		return 1;
	}

	data_a = mmap(NULL, stat_a.st_size, PROT_READ, MAP_SHARED, fd_a, 0);
	if (data_a == MAP_FAILED) {
		perror(NULL);
		return 1;
	}
	data_b = mmap(NULL, stat_b.st_size, PROT_READ, MAP_SHARED, fd_b, 0);
	if (data_b == MAP_FAILED) {
		perror(NULL);
		return 1;
	}

	if (verbose) {
		int i;

		printf("A: \"");
		for (i = 0; i < stat_a.st_size; ++i) {
			printf("%c", data_a[i]);
		}
		printf("\"\n");

		printf("B: \"");
		for (i = 0; i < stat_b.st_size; ++i) {
			printf("%c", data_b[i]);
		}
		printf("\"\n");
	}


	/* Real work starts here */

	struct result_container rc;
	int *L;
	long size_a = stat_a.st_size;
	long size_b = stat_b.st_size;
	int i, j;


	/*
	 * L[] is a one-dimensional array. So, we have to map our two-dimensional
	 * coordinates into that array. But that is often better than using a
	 * two-dimensional array, where you have to allocate more memory, need an
	 * extra memory access to find an element, and loose knowledge regarding the
	 * relative layout of individual lines.
	 *
	 * And we use calloc() instead of malloc() although the algorithm does not
	 * need this. But this way, all the memory has been touched once and all pages
	 * have been mapped, so that the first run of this algorithm is not slowed down
	 * due to page faults.
	 */
	L = calloc( size_a * size_b, sizeof(*L) );
	if (L == NULL) {
		fprintf(stderr, "calloc() failed\n");
		return 1;
	}

	init_result_container(&rc, data_a, data_b);
    
    struct timeval begin, end;
    
    gettimeofday(&begin, NULL);
    
	/* The actual algorithm */
	for (i = 0; i < size_a; ++i) {
		for (j = 0; j < size_b; ++j) {
			if (data_a[i] == data_b[j]) {
				if (i == 0 || j == 0)
					L[i * size_b + j] = 1;
				else
					L[i * size_b + j] = L[(i-1) * size_b + (j-1)] + 1;
			} else {
				L[i * size_b + j] = 0;
			}
		}
	}

	for (i = 0; i < size_a; ++i) {
		for (j = 0; j < size_b; ++j) {
			if (L[i * size_b + j] >= K) {
				if( i+1 < size_a && j+1 < size_b &&
						L[i * size_b + j] < L[(i+1) * size_b + (j+1)])
					continue;

				collect_result(&rc, i, j, L[i * size_b + j]);
			}
		}
	}
	gettimeofday(&end, NULL);
	
    if (end.tv_usec < begin.tv_usec) {
        end.tv_usec += 1000000;
        begin.tv_sec += 1;
    }
    double time = (end.tv_sec - begin.tv_sec) +
        (end.tv_usec-begin.tv_usec)/1000000.0;
    printf("time: %f\n", time);
    
	/* Output */
	print_results(&rc, verbose);

	/* Cleanup */
	free(L);

	munmap(data_a, 0);
	munmap(data_b, 0);

	close(fd_a);
	close(fd_b);

	return 0;
}
